package com.hc.programming.贪心;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
 * 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
 * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
 * 以这种方式修改数组后，返回数组 可能的最大和 。
 * <p>
 * 示例 1：
 * 输入：nums = [4,2,3], k = 1
 * 输出：5
 * 解释：选择下标 1 ，nums 变为 [4,-2,3] 。
 * 示例 2：
 * 输入：nums = [3,-1,0,2], k = 3
 * 输出：6
 * 解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
 * 示例 3：
 * 输入：nums = [2,-3,-1,5,-4], k = 2
 * 输出：13
 * 解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
 * <p>
 * 提示：
 * 1 <= nums.length <= 10^4
 * -100 <= nums[i] <= 100
 * 1 <= k <= 10^4
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/9/4 15:59
 */
public class K次取反后最大化的数组和 {
    public static void main(String[] args) {
        System.out.println("[4,2,3],1=5,--" + largestSumAfterKNegations(new int[]{4, 2, 3}, 1));
        System.out.println("[3,-1,0,2],3=6,--" + largestSumAfterKNegations(new int[]{3, -1, 0, 2}, 3));
        System.out.println("[2,-3,-1,5,-4],2=13,--" + largestSumAfterKNegations(new int[]{2, -3, -1, 5, -4}, 2));
        System.out.println("[8,-7,-3,-9,1,9,-6,-9,3],8=53,--" + largestSumAfterKNegations(new int[]{8, -7, -3, -9, 1, 9, -6, -9, 3}, 8));
        System.out.println("[-4,-2,-3],4=5,--" + largestSumAfterKNegations(new int[]{-4, -2, -3}, 4));
        System.out.println("[-28,-19,-13,5,-12,-27,0,29,-2,-6],2=37,--" + largestSumAfterKNegations(new int[]{-28, -19, -13, 5, -12, -27, 0, 29, -2, -6}, 2));
    }

    public static int largestSumAfterKNegations(int[] nums, int k) {
//        return 贪心(nums, k);
//        return 贪心2(nums, k);
        return 贪心3(nums, k);
    }

    private static int 贪心3(int[] nums, int k) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (k > 0 && nums[i] < 0) {
                k--;
                nums[i] = -nums[i];
            }
            sum += nums[i];
        }
        Arrays.sort(nums);
        return (k % 2 == 0) ? sum : (sum - 2 * nums[0]);
    }

    private static int 贪心2(int[] nums, int k) {
        sortByAbsolute(nums);
        int sum = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            if (k > 0 && nums[i] < 0) {
                k--;
                sum -= nums[i];
            } else {
                sum += nums[i];
            }
        }
        if (k % 2 == 0) {
            sum += nums[0];
        } else {
            sum -= nums[0];
        }
        return sum;
    }

    /**
     * 按绝对值大小排序
     */
    private static void sortByAbsolute(int[] nums) {
//        Arrays.sort(nums, (a,b)-> (Math.abs((Integer) a) - Math.abs((Integer) b)));
        冒泡排序(nums);
    }

    private static void 冒泡排序(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (Math.abs(nums[j]) > Math.abs(nums[j + 1])) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    private static int 贪心(int[] nums, int k) {
        Arrays.sort(nums);
        int sum = 0;
        int negative = nums.length; // 负数个数
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                negative = i;
                break;
            }
        }
        while (k > negative) {
            if (k - 2 < negative) {
                if (negative == nums.length || (k - 2 >= 0 && -nums[k - 2] < nums[negative])) {
                    k -= 2;
                }
                break;
            }
            k -= 2;
        }
        for (int n : nums) {
            if (k > 0) {
                sum -= n;
                k--;
            } else {
                sum += n;
            }
        }
        return sum;
    }
}
